package com.gorkr;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 正整数子集和等于sum的子集个数
 *
 * @author gorkr
 * @date 2021/12/29 16:03
 * <p>
 * 剪枝思路：
 * 1、has>sum剪枝
 * 2、has+r<sum剪枝
 **/

/**
 * 状态
 */
class State {
    int w;  //第几个整数
    boolean b;  // 是否加入子集
    int has;  // 当前子集和
    int r;  // 当前剩余和

    public State(int w, boolean b, int has, int r) {
        this.w = w;
        this.b = b;
        this.has = has;
        this.r = r;
    }
}


public class SubSetSum {

    /**
     *
     * @param wList 正整数集合
     * @param sum 要凑出的证书
     * @return 几种方案
     */
    public int solution(int[] wList, int sum) {
        List<Integer> subSet = new LinkedList<>();
        int size = wList.length;

        // 剩余和
        int r = Arrays.stream(wList).sum();
        // 子集方案数目
        int res = 0;
        State now = null;

        // 广度优先所用的队列
        Queue<State> queue = new LinkedList<>();
        // 当前处理的W1
        queue.offer(new State(-1, false,0,r));
        while (true){
            while (!queue.isEmpty()) {
                now = queue.poll();
                if(now.has>sum){
                    break;
                }else if(now.has==sum){
                    res++;
                    break;
                }
                else {

                    if(now.has+now.r>sum){
                        // 1
                        queue.offer(new State(now.w + 1, true,now.has+wList[now.w + 1], now.r-wList[now.w + 1]));
                        // 0
                        queue.offer(new State(now.w + 1,false,now.has, now.r-wList[now.w + 1]));
                    }

                }


            }
            if(queue.isEmpty()){
                break;
            }


        }

        return res;
    }

    @Test
    public void test() {
        int[] a = {11, 13, 24, 7};
        System.out.println(solution(a, 31));
    }
}
    